#include<bits/stdc++.h>
using namespace std;
const int NN=1004;
int n,q,a[NN],le[NN],ri[NN],sta[NN],f[NN][NN],vis[NN][NN];
int dp(int l,int r)
{
	int&d=f[l][r];
    if(vis[l][r]!=q)
    {
		d=0;
		vis[l][r]=q;
	}
    if(d)
		return d;
    if(l==0&&r==n+1)
		d=0;
    else if(a[l]<a[r])
		d=dp(le[l],r)+1;
    else if(a[l]>a[r])
		d=dp(l,ri[r])+1;
    else
		d=dp(le[l],ri[r])+1;
    return d;
}
int main()
{
    freopen("summer.in","r",stdin);
    freopen("summer.out","w",stdout);
	int k;
	scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    	scanf("%d",&a[i]);
    scanf("%d",&q);
    a[0]=a[n+1]=1e9;
    while(q--)
	{
        int x,l,r;
        scanf("%d%d%d",&x,&l,&r);
        swap(a[x],a[x+1]);
        int tot=1;
        sta[tot]=0;
        for(int i=1;i<=n;i++)
		{
            while(a[i]>=a[sta[tot]])
				tot--;
            le[i]=sta[tot];
            sta[++tot]=i;
        }
        tot=1; 
        sta[tot]=n+1;
        for(int i=n;i;i--)
		{
            while(a[i]>=a[sta[tot]])
				tot--;
            ri[i]=sta[tot];
            sta[++tot]=i;
        }
        long long ans=0;
        for(int i=l;i<=r;i++)
            ans+=1ll*dp(le[i],ri[i])*k+n-1;
        printf("%lld\n",ans);
    }
    return 0;
}
